1. Field of the Invention
The present invention relates to digital signal generators and more particularly to improved Direct Digital Frequency Synthesizers (DDFS).
2. Background of the Prior Art
For many digital circuits, it is often necessary to generate a sequence of sample values of a sine or cosine function at a particular frequency that may be adjusted while the time interval between samples remains fixed. Circuits known as Direct Digital Frequency Synthesizers (DDFS) perform this function. Many conventional art DDFS's generate the sine and cosine values by performing a table-lookup in a read only memory (ROM) that contains the values of samples of a sine/cosine function at the required angle values, and then provide these values as the output. The sequence of desired angles is generated by a phase accumulator. More precisely, the phase accumulator produces a sequence of normalized angles that are used to address the ROM. The table-lookups are performed at a very precisely controlled rate, which is the sample rate, and the desired frequency of the generated sinusoid is determined by the rate, relative to this reference rate, at which angles generated by the phase accumulator cycle through a range of values corresponding to [0, 2π).
Although these prior art table-lookup DDFS's perform adequately for many purposes, the tables often are large and occupy a relatively large amount of chip area when implemented as integrated circuits. Various techniques have been developed to reduce the ROM table size, which is determined by the number of address bits (i.e., the most significant portion of the phase accumulator output) and the precision of (i.e., the number of bits representing) the sine/cosine outputs. Truncation of the phase accumulator output is usually employed in order to reduce the lookup table size, as this size will double with each additional bit in the table address word. This phase truncation, however, creates imperfections in the output sine/cosine function since a sine/cosine value corresponding to a truncated phase will correspond to an effective value that is different from the sine/cosine value at the exact angle. Furthermore, the truncated phase accumulator values can be viewed as values obtained by adding some sequence of error terms to the sequence of exact angle values. Furthermore, the finite precision of the sine/cosine outputs contributes additional error terms. Thus, the output of the table-lookup process will consist of the superposition of the sine/cosine signal at the desired frequency and various other frequencies that result from the processing of the truncated phase sequence by the table-lookup and the finite precision sine/cosine outputs. These undesired frequency components are referred to as “spurious frequencies,” or “spurs.” The amplitude of these spurs should be small, and the quality of the DDFS is often assessed by determining how small the amplitudes of the spurs are. The “spurious free dynamic range” is the difference between the amplitude of the desired sinusoid and that of the largest spur. It is usually measured in decibels (dB).
One prior art technique for generating trigonometric functions such as sine and cosine, developed in the 1950's and known as CORDIC, avoids ROM table-lookups. CORDIC calculates the sine and cosine values of a particular angle through a series of rotations of a point in the complex plane, initially coincident with the X-axis on the unit circle. The X-axis and the Y-axis coordinates, representing the real and imaginary parts of a complex-valued number, at the final angle are the desired cosine and sine values, respectively.
However, according to the conventional CORDIC methodology, at each rotation it must be determined whether to rotate clockwise or counter-clockwise, where a counter-clockwise rotation corresponds to αi=1 and a clockwise rotation corresponds to αi=−1. CORDIC tries to approximate an angle θ as a sum of subangles Σθi. At each stage, if the approximation generated by all previous stages is larger than the desired angle θ, then the current stage decreases the value of the approximation by θi; otherwise the approximation is increased by θi. Thus, at each stage the direction of the rotation is chosen such that the error between the desired angle θ and the approximation is reduced. In CORDIC, the αi coefficients (which determine the direction of the rotation) are determined iteratively for each rotation stage and each one requires a comparator or its equivalent.
An improved DDFS is shown in U.S. Pat. No. 5,737,253, assigned to the assignee of the present invention, which is incorporated herein in its entirety. This improved DDFS provides a high-speed DDFS integrated circuit with high precision sine and cosine output data and a chip area smaller than could then be obtained using table-lookup-based or CORDIC approaches to the DDFS. A phase accumulator provides a sequence of angles to a sine/cosine generator that outputs a sequence of values of the sine/cosine function at a desired frequency. The sine/cosine generator includes a plurality of multiplierless butterfly and carry-save adder stages in cascade that perform angle rotations to calculate the sine and cosine values for each desired angle. The angle rotations are chosen to implement a series of transformations that result in closer and closer approximations to the sine and cosine values of the desired angle.
Multipliers may be eliminated from butterfly stages by taking advantage of the approximation tan θk≈θk. For sufficiently small θk (i.e., for sufficiently large k) the approximationtan θk≈θk=2−k  (1)reduces the corresponding multiplications performed by the butterfly stages to simple shift operations by a fixed number of bits (k bits). This approximation causes no loss of accuracy in the tan θk representation so long as tan θk is sufficiently small that the difference (θk−tan θk) is smaller than the finite-precision limits of the output data.
A multiplexer provides sine and cosine values for an angle that is the algebraic sum of the first M subangles θk that are not sufficiently small to employ the approximation tan θk≈θk. The subangles become successively smaller for each successive stage and the remaining subangles after these first M subangles satisfy the approximation tan θk≈θk to a desired accuracy. The sine and cosine values provided by the multiplexer are then input to the subsequent rotation stages, which perform the subsequent rotations to calculate the sine and cosine values for the desired angle. Rather than using a multiplexer, a small ROM table can also be used to perform the same function.
Only angles within a quadrant or within an octant, e.g. [0, π/4], need be provided to the rotation stages and the sine and cosine values for any angle in [0, 2π) can be computed from these angles by well-known trigonometric identities. Techniques are disclosed in U.S. Pat. No. 5,737,253 for converting an angle in [0, 2π) to a related angle in [0, π/4], performing the previously described rotations to calculate sine and cosine values for the transformed angle, and then deriving the sine and cosine values for the original angle in [0, 2π) from the sine and cosine values for the transformed angle in [0, π/4].
To summarize, an angle θ=b1θ1+b2θ2+ . . . +bNθN is generated where bk ε {0,1} are binary bits and the θk=2−k are the associated positional weights. Next, the sine and cosine values for a subangle ω, the algebraic sum of the first M rotation angles of θ, are obtained through a multiplexer or similar device (e.g., ROM table). Subangle ω may be chosen such that the remaining subangles that are processed may utilize the approximation tan θk≈θk and the binary bk ε {0,1} are recoded into signed digits rk ε {−1,+1} for an arbitrary angle θ by the mapping rk=2bk-1−1. The following transformation formulae are then used:Xk=Xk−1−rk2−kYk−1 and Yk=Yk−1+rk2−kXk−1  (2)where Xk−1 is the cosine value and Yk−1 is the sine value. The determined Xk cosine value and Yk sine value are then successively provided as the Xk−1 and Yk−1 inputs to subsequent transformation formulae until the desired accuracy is reached.
The number of rotation stages required by both the CORDIC and the Modified CORDIC algorithms are comparable to one another. In every butterfly stage, the CORDIC and the Modified CORDIC angle decompositions, equations (3) and (4), respectively, both require a nonzero rotation either in the positive or negative direction,
                              ω          =                                    ∑                              i                =                1                            N                        ⁢                                          σ                i                            ⁢                              ω                i                                                    ,                            (        3        )            where σi ε {−1,+1}, ωi=arctan 2−i for CORDIC and ωi=2−1 for Modified CORDIC,
                                          ω            =                          ϕ              +                                                ∑                                      i                    =                    2                                                        N                    +                    1                                                  ⁢                                                      r                    i                                    ⁢                                      ω                    i                                                                                ,                                    with              ⁢                                                          ⁢                              r                i                                      ∈                                          {                                                      -                    1                                    ,                                      +                    1                                                  }                            ⁢                                                          ⁢              and                                      ⁢                                  ⁢                  ϕ          =                                                    ∑                                  i                  =                  2                                                  N                  +                  1                                            ⁢                              ω                i                                      =                                          1                2                            -                                                1                                      2                                          N                      +                      1                                                                      .                                                                        (        4        )            
For the CORDIC and the Modified CORDIC algorithms these nonzero rotations are necessary (i.e., σi≠0) to facilitate the creation of the “rotation-angle-independent-constant”
  K  =            ∏              i        =        1            N        ⁢          cos      ⁢                          ⁢              ω        i            in equations (6) and (7) from the cos σiωi terms factored out of the butterfly stages in equation (5). Equation (7) reflects the CORDIC angle decomposition ωi=arctan 2−i.
                              [                                                                      cos                  ⁢                                                                          ⁢                  ω                                                                                                      sin                  ⁢                                                                          ⁢                  ω                                                              ]                =                              [                                                                                cos                    ⁢                                                                                  ⁢                                          σ                      N                                        ⁢                                          ω                      N                                                                                                                                  -                      sin                                        ⁢                                                                                  ⁢                                          σ                      N                                        ⁢                                          ω                      N                                                                                                                                        sin                    ⁢                                                                                  ⁢                                          σ                      N                                        ⁢                                          ω                      N                                                                                                            cos                    ⁢                                                                                  ⁢                                          σ                      N                                        ⁢                                          ω                      N                                                                                            ]                    ⁢                                          ⁢                      …            ⁢                                                  [                                                                                cos                    ⁢                                                                                  ⁢                                          σ                      i                                        ⁢                                          ω                      i                                                                                                                                  -                      sin                                        ⁢                                                                                  ⁢                                          σ                      i                                        ⁢                                          ω                      i                                                                                                                                        sin                    ⁢                                                                                  ⁢                                          σ                      i                                        ⁢                                          ω                      i                                                                                                            cos                    ⁢                                                                                  ⁢                                          σ                      i                                        ⁢                                          ω                      i                                                                                            ]                    ⁢                                          ⁢                                    …              ⁢                                                          [                                                                                          cos                      ⁢                                                                                          ⁢                                              σ                        1                                            ⁢                                              ω                        1                                                                                                                                                -                        sin                                            ⁢                                                                                          ⁢                                              σ                        1                                            ⁢                                              ω                        1                                                                                                                                                        sin                      ⁢                                                                                          ⁢                                              σ                        1                                            ⁢                                              ω                        1                                                                                                                        cos                      ⁢                                                                                          ⁢                                              σ                        1                                            ⁢                                              ω                        1                                                                                                        ]                        ⁡                          [                                                                    1                                                                                        0                                                              ]                                                          (        5        )                                          [                                                                      cos                  ⁢                                                                          ⁢                  ω                                                                                                      sin                  ⁢                                                                          ⁢                  ω                                                              ]                =                              [                                                            1                                                                                            -                                              σ                        N                                                              ⁢                    tan                    ⁢                                                                                  ⁢                                          ω                      N                                                                                                                                                              σ                      N                                        ⁢                    tan                    ⁢                                                                                  ⁢                                          ω                      N                                                                                        1                                                      ]                    ⁢                                          ⁢                      …            ⁢                                                  [                                                            1                                                                                            -                                              σ                        i                                                              ⁢                    tan                    ⁢                                                                                  ⁢                                          ω                      i                                                                                                                                                              σ                      i                                        ⁢                    tan                    ⁢                                                                                  ⁢                                          ω                      i                                                                                        1                                                      ]                    ⁢                                          ⁢                                    …              ⁢                                                          [                                                                    1                                                                                                      -                                                  σ                          1                                                                    ⁢                      tan                      ⁢                                                                                          ⁢                                              ω                        1                                                                                                                                                                                σ                        1                                            ⁢                      tan                      ⁢                                                                                          ⁢                                              ω                        1                                                                                                  1                                                              ]                        ⁡                          [                                                                    K                                                                                        0                                                              ]                                                          (        6        )                                          [                                                                      cos                  ⁢                                                                          ⁢                  ω                                                                                                      sin                  ⁢                                                                          ⁢                  ω                                                              ]                =                              [                                                            1                                                                                            -                                              σ                        N                                                              ⁢                                                                                  ⁢                                          2                                              -                        N                                                                                                                                                                                    σ                      N                                        ⁢                                                                                  ⁢                                          2                                              -                        N                                                                                                              1                                                      ]                    ⁢                                          ⁢                      …            ⁢                                                  [                                                            1                                                                                            -                                              σ                        N                                                              ⁢                                                                                  ⁢                                          2                                              -                        i                                                                                                                                                                                    σ                      N                                        ⁢                                                                                  ⁢                                          2                                              -                        i                                                                                                              1                                                      ]                    ⁢                                          ⁢                                                    …                ⁢                                                                  [                                                                            1                                                                                                                -                                                      σ                            N                                                                          ⁢                                                                                                  ⁢                                                  2                                                      -                            1                                                                                                                                                                                                                            σ                          N                                                ⁢                                                                                                  ⁢                                                  2                                                      -                            1                                                                                                                                      1                                                                      ]                            ⁡                              [                                                                            K                                                                                                  0                                                                      ]                                      .                                              (        7        )            
If one permits σi to also take on the value of zero, then the necessary condition cos σiωi=cos ωi for constant K will not hold when a σi=0. Similarly, for the Modified CORDIC algorithm, the nonzero rotations are necessary (i.e., ri≠0) to produce the “rotation-angle-independent-constant”
  K  =            ∏              i        =        2                    N        +        1              ⁢          cos      ⁢                          ⁢              ω        i            in equations (9), (10), and (11), by the factored out cos riωi terms from the butterfly stages in equation (8) and carrying out the multiplication
            [                                                  cos              ⁢                                                          ⁢              ϕ                                                                          -                sin                            ⁢                                                          ⁢              ϕ                                                                          sin              ⁢                                                          ⁢              ϕ                                                          cos              ⁢                                                          ⁢              ϕ                                          ]        ⁡          [                                    1                                                0                              ]        =            [                                                  cos              ⁢                                                          ⁢              ϕ                                                                          sin              ⁢                                                          ⁢              ϕ                                          ]        .  If any ri is allowed to take on the value of zero, then the necessary condition cos riωi=cos ωi for the constant K will not hold. From these observations one may deduce that reducing the total number of rotations may be infeasible since “no rotation” corresponds to σi=0 or ri=0.
                              [                                                                      cos                  ⁢                                                                          ⁢                  ω                                                                                                      sin                  ⁢                                                                          ⁢                  ω                                                              ]                =                              [                                                                                cos                    ⁢                                                                                  ⁢                                          r                                              N                        +                        1                                                              ⁢                                          ω                                              N                        +                        1                                                                                                                                                        -                      sin                                        ⁢                                                                                  ⁢                                          r                                              N                        +                        1                                                              ⁢                                          ω                                              N                        +                        1                                                                                                                                                              sin                    ⁢                                                                                  ⁢                                          r                                              N                        +                        1                                                              ⁢                                          ω                                              N                        +                        1                                                                                                                                  cos                    ⁢                                                                                  ⁢                                          r                                              N                        +                        1                                                              ⁢                                          ω                                              N                        +                        1                                                                                                                  ]                    ⁢                                          ⁢                                                    …                ⁢                                                                  [                                                                                                    cos                        ⁢                                                                                                  ⁢                                                  σ                          2                                                ⁢                                                  ω                          2                                                                                                                                                              -                          sin                                                ⁢                                                                                                  ⁢                                                  r                          2                                                ⁢                                                  ω                          2                                                                                                                                                                        sin                        ⁢                                                                                                  ⁢                                                  σ                          2                                                ⁢                                                  ω                          2                                                                                                                                    cos                        ⁢                                                                                                  ⁢                                                  r                          2                                                ⁢                                                  ω                          2                                                                                                                    ]                            ⁡                              [                                                                                                    cos                        ⁢                                                                                                  ⁢                        ϕ                                                                                                                                      -                          sin                                                ⁢                                                                                                  ⁢                        ϕ                                                                                                                                                sin                        ⁢                                                                                                  ⁢                        ϕ                                                                                                            cos                        ⁢                                                                                                  ⁢                        ϕ                                                                                            ]                                      ⁡                          [                                                                    1                                                                                        0                                                              ]                                                          (        8        )                                          [                                                                      cos                  ⁢                                                                          ⁢                  ω                                                                                                      sin                  ⁢                                                                          ⁢                  ω                                                              ]                =                              [                                                            1                                                                                            -                                              r                                                  N                          +                          1                                                                                      ⁢                    tan                    ⁢                                                                                  ⁢                                          ω                                              N                        +                        1                                                                                                                                                                                    r                                              N                        +                        1                                                              ⁢                    tan                    ⁢                                                                                  ⁢                                          ω                                              N                        +                        1                                                                                                              1                                                      ]                    ⁢                                          ⁢                      …            ⁢                                                  [                                                            1                                                                                            -                                              r                        i                                                              ⁢                    tan                    ⁢                                                                                  ⁢                                          ω                      i                                                                                                                                                              r                      i                                        ⁢                    tan                    ⁢                                                                                  ⁢                                          ω                      i                                                                                        1                                                      ]                    ⁢                                          ⁢                                    …              ⁢                                                          [                                                                    1                                                                                                      -                                                  r                          2                                                                    ⁢                                                                                          ⁢                      tan                      ⁢                                                                                          ⁢                                              ω                        2                                                                                                                                                                                r                        2                                            ⁢                                                                                          ⁢                      tan                      ⁢                                                                                          ⁢                                              ω                        2                                                                                                  1                                                              ]                        ⁡                          [                                                                                          K                      ⁢                                                                                          ⁢                      cos                      ⁢                                                                                          ⁢                      ϕ                                                                                                                                  K                      ⁢                                                                                          ⁢                      sin                      ⁢                                                                                          ⁢                      ϕ                                                                                  ]                                                          (        9        )                                          [                                                                      cos                  ⁢                                                                          ⁢                  ω                                                                                                      sin                  ⁢                                                                          ⁢                  ω                                                              ]                =                              [                                                            1                                                                                            -                                              r                                                  N                          +                          1                                                                                      ⁢                    tan                    ⁢                                                                                  ⁢                                          2                                              -                                                  (                                                      N                            +                            1                                                    )                                                                                                                                                                                                            r                                              N                        +                        1                                                              ⁢                    tan                    ⁢                                                                                  ⁢                                          2                                              -                                                  (                                                      N                            +                            1                                                    )                                                                                                                                      1                                                      ]                    ⁢                                          ⁢                      …            ⁢                                                  [                                                            1                                                                                            -                                              r                        i                                                              ⁢                    tan                    ⁢                                                                                  ⁢                                          2                                              -                        i                                                                                                                                                                                    r                      i                                        ⁢                    tan                    ⁢                                                                                  ⁢                                          2                                              -                        i                                                                                                              1                                                      ]                    ⁢                                          ⁢                                    …              ⁢                                                          [                                                                    1                                                                                                      -                                                  r                          i                                                                    ⁢                                                                                          ⁢                      tan                      ⁢                                                                                          ⁢                                              2                                                  -                          2                                                                                                                                                                                                        r                        i                                            ⁢                                                                                          ⁢                      tan                      ⁢                                                                                          ⁢                                              2                                                  -                          2                                                                                                                          1                                                              ]                        ⁡                          [                                                                                          K                      ⁢                                                                                          ⁢                      cos                      ⁢                                                                                          ⁢                      ϕ                                                                                                                                  K                      ⁢                                                                                          ⁢                      sin                      ⁢                                                                                          ⁢                      ϕ                                                                                  ]                                                          (        10        )                                          [                                                                      cos                  ⁢                                                                          ⁢                  ω                                                                                                      sin                  ⁢                                                                          ⁢                  ω                                                              ]                =                              [                                                            1                                                                                            -                                              r                                                  N                          +                          1                                                                                      ⁢                                                                                  ⁢                                          2                                              -                                                  (                                                      N                            +                            1                                                    )                                                                                                                                                                                                            r                                              N                        +                        1                                                              ⁢                                          2                                              -                                                  (                                                      N                            +                            1                                                    )                                                                                                                                      1                                                      ]                    ⁢                                          ⁢                      …            ⁢                                                  [                                                            1                                                                                            -                                              r                                                  β                          +                          1                                                                                      ⁢                                                                                  ⁢                                          2                                              -                                                  (                                                      β                            +                            1                                                    )                                                                                                                                                                                                            r                                              β                        +                        1                                                              ⁢                                          2                                              -                                                  (                                                      β                            +                            1                                                    )                                                                                                                                      1                                                      ]                    ×                      [                                                            1                                                                                            -                                              r                        β                                                              ⁢                    tan                    ⁢                                                                                  ⁢                                          2                                              -                        β                                                                                                                                                                                    r                      β                                        ⁢                    tan                    ⁢                                                                                  ⁢                                          2                                              -                        β                                                                                                              1                                                      ]                    ⁢                                          ⁢                                    …              ⁢                                                          [                                                                    1                                                                                                      -                                                  r                          2                                                                    ⁢                      tan                      ⁢                                                                                          ⁢                                              2                                                  -                          2                                                                                                                                                                                                        r                        2                                            ⁢                      tan                      ⁢                                                                                          ⁢                                              2                                                  -                          2                                                                                                                          1                                                              ]                        ⁡                          [                                                                                          K                      ⁢                                                                                          ⁢                      cos                      ⁢                                                                                          ⁢                      ϕ                                                                                                                                  K                      ⁢                                                                                          ⁢                      sin                      ⁢                                                                                          ⁢                      ϕ                                                                                  ]                                                          (        11        )            
What is needed is a DDFS design which improves on the conventional DDFS designs by, for example, reducing the number of stages requiring rotation.